package com.linyaonan.leetcode.medium._22;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * <p>
 * 例如，给出 n = 3，生成结果为：
 * <p>
 * [
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 *
 * @author: Lin
 * @date: 2020/1/15
 */
public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    private void backtrack(List<String> ans, String cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }
        // 左括号小于等于n
        if (open < max) {
            backtrack(ans, cur + "(", open + 1, close, max);
        }
        // 右括号必须要小于左括号才有增加的必要性，不然不能形成完整的闭合
        if (close < open) {
            backtrack(ans, cur + ")", open, close + 1, max);
        }
    }
}
